\ifx\wholebook\relax \else

\documentclass[UTF8]{article}

\usepackage[cn]{../../prelude}

\setcounter{page}{1}

\begin{document}

\title{递归}

\author{刘新宇
\thanks{{\bfseries 刘新宇} \newline
  Email: liuxinyu95@gmail.com \newline}
  }

\maketitle
\fi

\markboth{递归}{编程中的数学}

\chapter*{倒水趣题完整程序}
\phantomsection  % so hyperref creates bookmarks
\addcontentsline{toc}{chapter}{倒水趣题完整程序}

求得两个瓶子倒水的次数后，就可以生成一系列倒水的步骤，将这些步骤像表(\ref{tab:designed-jugs-ops})一样输出。

\lstset{frame=single}
\begin{lstlisting}
-- Populate the steps
water a b c = if x > 0 then pour a x b y
              else map swap $ pour b y a x
  where
    (x, y) = jars a b c

-- Pour from a to b, fill a for x times, and empty b for y times.
pour a x b y = steps x y [(0, 0)]
  where
    steps 0 0 ps = reverse ps
    steps x y ps@((a', b'):_)
      | a' == 0 = steps (x - 1) y ((a, b'):ps)  -- fill a
      | b' == b = steps x (y + 1) ((a', 0):ps)  -- empty b
      | otherwise = steps x y ((max (a' + b' - b) 0,
                                min (a' + b') b):ps) -- a to b
\end{lstlisting}

运行这一程序，输入\texttt{water 9 4 6}就可以得到最佳的倒水步骤:

\begin{verbatim}
[(0,0),(9,0),(5,4),(5,0),(1,4),(1,0),(0,1),(9,1),(6,4),(6,0)]
\end{verbatim}

\ifx\wholebook\relax \else
%
\expandafter\enddocument
%\end{document}

\fi
